package com.base.dynamicprograming;

/**
 * TODO
 *
 * @author leon
 * @date 2021年12月13日 14:26
 */
public class UniquePathsWithObstacles {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        // 假设入口没有障碍物
        dp[0][0] = 1;
        for(int i = 0;i<m;i++){
            for(int j =0 ;j<n;j++){
                // 入口也可能放障碍物，对（0，0）从新赋值
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                    continue;
                }

                if(i>0&&j>0){
                    dp[i][j] = dp[i-1][j] +dp[i][j-1];
                }else if(i>0){
                    dp[i][j] = dp[i-1][j];
                }else if(j>0){
                    dp[i][j] = dp[i][j-1];
                }

            }
        }

        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        System.out.println(new UniquePathsWithObstacles().uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));

    }
}
